The present invention relates generally to scheduling models and, in an embodiment described herein, more particularly provides a multi-tier cross-department scheduling model for order processing operations.
A hypothetical Company B will be used herein to demonstrate the types of problems faced in typical complex order processing operations. Suppose, for example, that Company B is the industry leader in rentable DVD and game media with over 9,000 stores worldwide (over 5,600 in the United States including franchisees) and over $5.8 billion in annual revenue for fiscal year 2005 (over $3.9 billion in the United States including franchisees). The data used in this application is specific to the United States order processing and distribution operations and does not include any international activities.
The DVD and electronic game industries are highly peculiar when compared to others as they are characterized by an extremely compressed life cycle due to the release date structure imposed by the movie studios and to the short active life span inherent in any entertainment media product. As such it is very customary to see a great majority of sales activity in the first week a specific title is offered with very little activity in subsequent weeks. The only exception to this pattern would be titles that have a seasonal aspect such as Holiday genre as the individual holidays approach (for example Horror movies as Halloween approaches) or if there are complimentary titles offered (such as a part 3 of a movie trilogy causing increased activity for parts 1 and 2).
In this sense it is convenient to look at the industry as one with 52 distinct “seasons” as the new release offerings change on a weekly basis. We find from history that these weekly “seasons” have virtually no correlation with each other but there is a weak correlation to the calendar seasons. An example of the life cycle for a single product along with Company B's niche can be seen in the FIG. 1. It is important to notice that in both the theatrical release and the release on DVD the revenue decay curve is extremely steep.
We find that a product's life cycle can also take multiple paths based on when/how it is being used. As seen in FIG. 2 a product can move from a high volume new release title (region I) to a low volume catalog title (region IV) through the normal decay curve. Also, when seasonal activity and complimentary titles are considered product can shift from low volume to high even for older titles (region IV to region II). Likewise some titles may never leave the low volume range even if it is a new release product (region III to region IV).
History has shown that due to the continually changing product mix, the weekly aggregate volumes can drop to as low as 50% from one week to the next or can just as easily double. Forecasting this change in volumes is difficult as each new product is truly a new release with no history, forcing the industry to predict activity based on historical performance of “similar products” as well as product performance in theatrical venues. However, even the best models result in a high degree of error.
To accommodate the supply chain requirements of this highly specialized industry, logistic networks in the game and DVD rental industry have adopted methods and processes that are flexible enough to handle this extreme level of volatility while creating methods and processes that are robust enough to virtually eliminate late product deliveries. This is critical in this industry as with a nearly nonexistent maturity/decline phase in the product life cycle, any delays in product delivery would have the net effect of eliminating any potential for revenue to be gained from the product. Simply stated, any late deliveries have a tremendous cost impact.
Company B, as an industry leader has pioneered many of the initiatives necessary to remain competitive in this arena. Focusing specifically on Company B's distribution organization we can see in the process flow diagram shown in FIG. 3 that Company B has developed a system of 12 picking/processing departments followed by a total of 9 merge/sortation points in addition to a recursive product infeed as the cornerstone for its distribution model.
This process flow diagram represents picking and processing departments denoted by a “P” (P1, P2, etc.), conveyor merge points denoted by an “M”, and system sortation points denoted by an “S.” Picking and production activities include activities that range from simple retail picking to light manufacturing where raw discs and artwork (received in bulk) are built into the rental units as found in Company B stores. Conveyor merge points are used to route multiple conveyor lines to a single conveyor, and sortation points are used to route containers from a single conveyor line to multiple lines/departments.
Here (FIG. 3) sortation point S1 is being used to sort outbound containers direct to individual shipping doors and sortation point S2 is being used to sort orders that have been picked/processed to locations in the consolidation department (M3). Ideally all product would flow through Merge 3 (M3) and would exit the system through sorter 1 (S1) using the recursive infeed through Merge 2 (M2) as shown by the bold arrows in FIG. 3.
If capacity constraints were exceeded at any of the merge/sortation points along the process we would expect product to exit the system as the capacity constraints were encountered (for example at M1, M2, S1, S2, M3, etc.), thereby bypassing subsequent system constraints. This “system bypass” potential is shown on FIG. 3 by the arrows at the merge/sortation points labeled as Xi,k,M1, Xi,k,M2, Xi,k,S1, Xi,k,S2, Xi,k,M3. The system bypass potential is undesirable as doing so would prevent containers from taking advantage of the consolidation process at merge point M3 which yields a much lower system cost by reducing the number of containers shipped. The nature of this consolidation relationship (merge M3) will be discussed more thoroughly below.
As cumbersome as these process flow diagrams appear, these are the result of multiple planned process improvement initiatives which are strategically designed to maximize throughput, while maintaining a very high level of flexibility and service level execution. In reality this process flow diagram is similar to environments that can be found at large “big box” retailers and package delivery companies.
Once orders are produced either through picking or manufacturing and exit the conveyor system, outbound containers are shipped to stores primarily through a pool point network of over 40 regional pool points. These regional pool points crossdock containers from the Company B distribution center to the stores. As Company B maintains one distribution facility and ships to over 5,600 stores within the United States, this “hub and spoke” design has proven to be more cost effective than creating multiple distribution facilities or shipping direct to stores.
It should be noted that shipping by pool point adds additional constraints (as each pool point location has a set weekly trailer departure schedule regardless of volume), and complexity (through having to coordinate with multiple carriers and pool point operators as they are regional in nature), with the trade off of a greatly reduced cost per piece shipped. The transit time from the distribution center to an individual store ranges from 2 to 7 days using the pool point shipping method (depending on region being shipped to) versus 1 to 5 days using other direct to store methods. Expense of shipping product using pool points is a fixed cost per container and is contract dependent.
For purposes of illustration, we will use an estimated cost of $2.50 per container shipped via pool point (independent of container dimension) and $6.00 as an estimated charge per container if the shipment is made direct to store (dependent on container dimension). Although we can already see the benefit here of using the pool point network ($2.50 vs. $6.00 per container), we will see during the problem formulation that the true benefit when combining pool points with a consolidation process dwarfs these initial cost savings.
From a complexity standpoint, a typical week in this environment can experience as many as 400 jobs which must be worked across 12 processing departments where individual jobs may be completed in anywhere from 1 to 5 different departments depending on job requirements which must then compete for capacity in up to 9 subsequent shared resources. The operating schedule consists of two 12 hour shifts per day across 6 days per week for a total of 12 shifts per week. As breaks, lunches, shift start up meetings, etc. must also be considered, we can normally assume 10.5 available production hours per employee per shift. Jobs that can be completed in multiple departments may experience higher processing costs in some departments over others. Roughly 5% of the overall demand is based on point of sale activity and 95% is based on forecasted allocation. Even though the 95% forecasted allocation is deterministic, the detailed planning window is still very short due to the nature of the business resulting in the need for a very flexible and dynamic solution.
Until now, the planning tools available at Company B were confined to the following—                1. A long range model (3-18 months) which plans aggregate activity for budgeting purposes;        2. An intermediate range model (1-3 months) which plans aggregate capacity by department (excluding merge/sortation constraints); and        3. A short range tactical model (1 week) which plans aggregate capacity by department (excluding merge/sortation constraints) including labor planning        
As a result of these three planning tools used at Company B, their distribution operation has been characterized by intermittent situations where capacity limits at critical nodes in the production and product handling processes have been exceeded due to unexpected activity spikes. Visibility to these activity spikes are typically known up to a couple of days in advance but as all scheduling previously took place in aggregate their ability to effectively control the operation at the discrete job level did not exist. This resulted in additional transportation costs, poor system utilization and a high cost of labor.
This problem as described at Company B is common in practice but has yet to be treated. Not only are there no available software packages on the market to address this problem, but there is also no available theoretical research on this topic.
There exists a great deal of literature regarding scheduling theory (Pinedo, 2002; Graves, 1981), most of which does not sufficiently address the problem stated above. Likewise, there is existing literature regarding scheduling models applied in practice (Brown et al. 2002; Moss et al. 2000; Olson et al. 2000) which, again, are different from the problem addressed in this application.
Dobson et al. (2001) deal with the problem of minimizing the scheduling cost (defined as the product of the holding cost and the flow time of a particular batch) which they state is similar to a weighted flow time. In doing so Dobson et al. consider an environment where jobs are organized into batches which must then be processed through a processing center. This is typical of many scheduling examples, however it does not consider parallel processing centers which must then compete for subsequent processing capacities.
Similarly, Kuchta et al. (2004) uses mixed integer programming to schedule parallel operations to maintain consistent output. Here their objective function is to minimize the sum of the excess production and the deficit production volume (not the net difference but rather the sum of “absolute values”). However, their approach does not address competition between multiple production departments which compete for shared downstream capacities.
Chen and Pundoor (2006) considers four problems with different cost related objective functions and assumes product that is time sensitive, with high variety, short life cycle and schedules them through parallel processing sites with a transportation cost. In this example Chen and Pundoor addresses an environment much more similar to what we find in this application (scheduling across production departments in parallel) but again stops short of addressing the possibility of the parallel departments competing for subsequent resources.
Keskinocak et al. (2002) state that they provide the first system to provide an integrated solution to consider interactions between different stages of the manufacturing and distribution process. In their application they use integer program formulation to maximize profit while meeting demand within specified time segments. They get past an integer programming hurdle (introduced by the need to prevent order splitting) through the use of a number of heuristic “fixes” and are successful in scheduling orders along a single serial path. They do not take into consideration an environment where orders are processed in parallel departments which must then compete for shared constrained resources.
Agnetis et al. (2004) also have an interesting problem where they present the goal of scheduling competing agents using a common resource. They use a set of nonpreemptive jobs to generate nondominating schedules which is a useful concept as this application also considers multiple jobs competing for a shared resource as one component of the stated problem. However the main focus for Agnetis et al. is to analyze the complexity of a number of scenarios where the objective function is to minimize the total weighted completion time and number of late jobs. They do not provide a solution or formulation to solve this problem, they merely analyze the complexity.
Watanabe et al. (2001) seek to schedule product through a shipping sorter, treated as a finite capacity queue, which is used to hold product until all outbound orders are present at which point they are shipped. They accomplish this through the use of a genetic algorithm. The problem that Watanabe et al. presents is one where orders that are fed into this queue must be properly sequenced before entering the system in order to prevent the queue from becoming filled with partial orders which consume physical space on the shipping sorter which reduces its effectiveness. This problem is quite different from the one presented in the present application as their model does not consider the possibility of scheduling multiple queues of this nature in series nor does it consider the scheduling of jobs across parallel departments as part of their order sequencing objective.
Chen and Vairaktarakis (2005) considers a situation where jobs are processed and then delivered to customers with no interim staging in an attempt to find a joint production and distribution schedule which optimizes an objective function. The stated goal of their objective function is to minimize the sum of the total distribution cost and a function measuring customer service. However, different from the problem for this application, Chen and Vairaktarakis do not consider an environment where the processing and distribution volumes are constrained. This is an aspect which is a necessity in this application.
Lee et al. (1996) and Pinto and Grossmann (1998) both present mixed integer linear programming models for petroleum and chemical processing applications. In both applications the common goal is to schedule a multiple stage environment where there are elements of parallel processing functions set up in series. However different from our application, their applications did not deal with the situation where there is competition for constrained subsequent resources.
Based on the available academic literature, a thorough evaluation of an environment where constrained parallel production competes for multiple levels of subsequent shared resources as found at Company B does not exist. In fact, the Company B operation is somewhat unique in how it mixes distribution with a heavy augmentation of light manufacturing and in how the change in product mix creates an increasingly more complex environment.
We should also point out here that the product life cycle at Company B differs greatly from traditional “big box” retailers, as these companies schedule activities based on a much smaller set of variables. Scheduling parameters at a big box retailer is typically confined to container picks, no production activities and very traditional and stable product seasonalities. Likewise SKU volatility is typically low, product life cycles are long and there are few strict in store date requirements. However, it should be noted that one significant aspect of the big box retailers environment is similar to what is found at Company B, specifically the parallel picking environment which competes for shared subsequent resources which is manifested in the form of multiple picking “modules” which proceed to a high speed sorter which separates product by shipping lane.
Even though the problem presented in this application exists in many companies today in one form or another, it is a problem that is often simply glossed over during discussions of operational improvement strategies. An example of this can be found in a white paper prepared by Dematic (formerly Rapistan), a premier logistics support/solutions provider which services large manufacturing companies. In their white paper they state that                “ . . . A properly executed wave management strategy will decrease order fulfillment time, boost productivity, and lower operational costs. Wave management is all about balancing and optimizing the work presented to the distribution center to perform: proper mix of small and large orders in a wave, # of expected containers, # of diverts off the sorter, etc. . . . ”        
This statement (“ . . . balancing and optimizing work presented . . . # of diverts off the sorter . . . ”) sounds promising, but in reality we find that the scheduling software packages available on the market today are either ERP tools which depend on a well disciplined delivery schedule or tools which treat subsequent constraints as time delays with infinite capacity.
Given this, it is clear that what is absent is a short range planning solution that schedules discrete jobs to parallel picking/processing departments while allowing preferred departments by job, in addition to taking into consideration that these parallel departments compete for subsequent shared resources (merge and sortation points) which have finite capacity. The solution would preferably include an improved level loading of the workload which reduces the cost of labor and increases available capacity, and would preferably be easily adaptable to a variety of organizations with similar short range scheduling needs.